// https://www.lintcode.com/problem/connecting-graph-iii/description

class ConnectingGraph3 {
public:
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    int *father;    
    int count;
    ConnectingGraph3(int n) {
        father = new int[n + 1];
        count = n;
        for (int i = 1; i <= n; ++i) {
            father[i] = i;
        }
    } 
    
    int find(int a)
    {
        int x = a;
        while(father[a] != a)
        {
            a = father[a];
        }
        while (x != a)
        {
            int tmp = father[x];
            father[x] = a;
            x = tmp;
        }
        return a;
    }
    
    void connect(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb)
        {
            father[fa] = fb;
            count--;
        }
    }

    /**
     * @return: An integer
     */
    int query() {
        return count;
    }
};